#include <bits/stdc++.h>
using namespace std;

//
// Created by lfm on 2025/3/23.
//
#include <bits/stdc++.h>

using namespace std;
struct TreeNode
{
    int val;
    TreeNode * left;
    TreeNode * right;
};

class Solution
{
public:
    void dfs(TreeNode* root, int & targetSum, int& ans, unordered_map<long long, int>& cnt, long long sum)
    {
        if (root == nullptr)
        {
            return;
        }
        sum += root->val;
        ans += cnt.find(sum - targetSum) != cnt.end() ? cnt[sum - targetSum] : 0;
        cnt[sum]++;
        dfs(root->left, targetSum, ans, cnt, sum);
        dfs(root->right, targetSum, ans, cnt, sum);
        cnt[sum]--;
    }

    int pathSum(TreeNode* root, int targetSum)
    {
        if (root == nullptr)
        {
            return 0;
        }
        unordered_map<long long, int> cnt;
        cnt[0] = 1;
        int ans = 0;
        dfs(root, targetSum, ans, cnt, 0);
        return ans;
    }
};
